#include <vector>

typedef std::vector< short>   vint;
typedef std::vector<bool>   vbool; 
typedef std::vector< std::vector<short> > vvint;
typedef std::vector< std::vector<bool> > vvbool;
typedef std::vector< std::vector< std::vector<short> > > vvvint;
typedef std::vector< std::vector< std::vector<bool> > > vvvbool;

short resolver( vvint& matriz, short n, short cota ) {
    vvvbool mem(n, vvbool(n, vbool(cota+1,false)));
    mem[0][0][matriz[0][0]] = true;
    short temp1, temp2;
    short actual;
    
    //marcar borde superior
    for(short j = 1; j < n; ++j){
		actual = matriz[0][j];
		vbool& ant = mem[0][j-1];
		vbool& act = mem[0][j];
		for(short k = 0; k <= cota; ++k){
			if(ant[k]){
				temp1 = k + actual;
				temp2 = k - actual;
				if (temp1 < 0) temp1 *= -1;
				if (temp2 < 0) temp2 *= -1;
				if (temp1 <= cota) act[temp1] = true;
				if (temp2 <= cota) act[temp2] = true;
			}
		}
	}
	//marcar borde izquierdo
	for(short i = 1; i < n; ++i){
		actual = matriz[i][0];
		vbool& ant = mem[i-1][0];
		vbool& act = mem[i][0];
		for(short k = 0; k <= cota; ++k){
			if(ant[k]){
				temp1 = k + actual;
				temp2 = k - actual;
				if (temp1 < 0) temp1 *= -1;
				if (temp2 < 0) temp2 *= -1;
				if (temp1 <= cota) act[temp1] = true;
				if (temp2 <= cota) act[temp2] = true;
			}
		}
	}
	
	//marcar casillas interiores
	for(short i = 1; i < n; ++i){
		for(short j = 1; j < n; ++j ){
			actual = matriz[i][j];
			vbool& izq = mem[i][j-1];
			vbool& sup = mem[i-1][j];
			vbool& act = mem[i][j];
			for(short k = 0; k <= cota; ++k){
				if(izq[k] || sup[k]){
					temp1 = k + actual;
					temp2 = k - actual;
					if (temp1 < 0) temp1 *= -1;
					if (temp2 < 0) temp2 *= -1;
					if (temp1 <= cota) act[temp1] = true;
					if (temp2 <= cota) act[temp2] = true;
				}
			}
		}
	}
	
	// busco el minimo
	for(short k = 0; k <= cota; ++k){
		if(mem[n-1][n-1][k]){
			return k;
		}
	}
    return -1;
}



int main() {
	
    short n;
    scanf ("%hd",&n);
    
    while ( n != 0 ) {
        vvint matriz(n, vint(n, 0));
        short cantElem = 0;
        short maxpiramide = 0;
		short valor;
		short x, y;
		short cota = 0;  
        for( short i = 0; i < (2*n - 1); ++i ){
            
            i < n ? ++cantElem : --cantElem;
    
            for( short j = 0; j < cantElem ; ++j ){
                scanf ("%hd",&valor);
                if (valor < 0) valor *= -1;
                if (i < n) {
                    y = i - j;
                    x = i - y;
                } else {
                    x = i + j - (n - 1);
                    y = i - x;
                }
                if (valor > maxpiramide) maxpiramide = valor;
                matriz[x][y] = valor;
            }
        }
        cota = n* maxpiramide;
        printf("%hd\n", resolver( matriz, n, cota));
		scanf ("%hd",&n);
    }
    
    return 0;
}


